package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/distinct-subsequences/
 * @create 2025/8/30 18:20
 * @since JDK17
 */

public class Solution26 {
    char[]s1, s2;
    int[][] dp;
    int f(int i, int j) {
        if (j == s2.length) {
            return 1;
        }
        if (i == s1.length) {
            return 0;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int ans = 0;
        if (s1[i] == s2[j]) {
            ans += f(i + 1, j + 1);
        }
        ans += f(i + 1, j);
        return dp[i][j] = ans;
    }
    int f2() {
        int n = s1.length, m = s2.length;
        for (int i = 0; i < m; i++) {
            dp[n - 1][i] = 0;
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = n - 2 ; i >= 0; i--) {
            for (int j = m - 2; j >= 0; j--) {
                dp[i][j] += dp[i + 1][j];
                if (s1[i] == s2[j]) {
                    dp[i][j] += dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }

    public int numDistinct(String str, String t) {
        s1 = str.toCharArray();
        s2 = t.toCharArray();
        dp = new int[s1.length][s2.length];
        for (int i = 0; i < s1.length; i++) {
            Arrays.fill(dp[i], -1);
        }
//        return f(0, 0);
        return f2();
    }
}
